package com.agile.leetcode.node.mergenode;

/**
 * 合并两个有序链表
 *
 * @Author KD
 * @Date 2021/1/18 13:46
 */
public class MergeSortList {
    public static void main(String[] args) {
        ListNode node9 = new ListNode(9, null);
        ListNode node7 = new ListNode(7, node9);
        ListNode node5 = new ListNode(5, node7);
        ListNode node3 = new ListNode(3, node5);
        ListNode node1 = new ListNode(1, node3);
        ListNode node10 = new ListNode(10, null);
        ListNode node8 = new ListNode(8, node10);
        ListNode node6 = new ListNode(6, node8);
        ListNode node4 = new ListNode(4, node6);
        ListNode node2 = new ListNode(2, node4);
        ListNode merge = merge(node1, node2);
        System.out.println(merge);
    }

    /**
     * 合并两个有序链表
     *
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode merge(ListNode l1, ListNode l2) {
        // 判断是否为空
        if (l1 == null) {
            return l1;
        }
        if (l2 == null) {
            return l2;
        }
        ListNode dummy = new ListNode(0, null);
        // 指针
        ListNode current = dummy;
        while (l1 != null && l2 != null) {
            // 比较器
            if (l1.value <= l2.value) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }
        // l1跑完了，剩余的部分编程l2
        if (l1 == null) {
            current.next = l2;
        }
        // l2跑完了，剩余的部分编程l1
        if (l2 == null) {
            current.next = l1;
        }
        return dummy.next;
    }
}

class ListNode {
    int value;
    ListNode next;

    public ListNode(int value, ListNode next) {
        this.value = value;
        this.next = next;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "value=" + value +
                ", next=" + next +
                '}';
    }
}
